package com.interview.javabasic.DataStructrue;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import com.interview.javabasic.JUC.A;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        //完成将中缀表达式转换为后缀表达式的功能
        String expression = "1+((2+3)*4)-5";
        List<String> list = toInfixExpressionList(expression);
        System.out.println("中缀表达式为："+list);
        List<String> suffix = parseSuffixExpressionList(list);
        System.out.println("后缀表达式为："+suffix);









        //先定义一个逆波兰表达式
        //为了方便，逆波兰表达式，数字和符合使用空格隔开
        String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
        /*
         * 1、先将“3 4 +5 +6 -”=》放到ArrayList中，
         * 2、将ArrayList传递给一个方法，遍历配合栈，完成计算
         * */
        /*List<String> ls = getListString(suffixExpression);
        System.out.println("rpnlist=>"+ls);
        int res = calculate(ls);
        System.out.println("计算的结果是="+res);*/
    }
    //转换为后缀表达式
    public static List<String> parseSuffixExpressionList(List<String> ls){
        //定义两个栈
        Stack<String> s1 = new Stack<>();
        //因为s2在整个转换过程中没有pop操作，使用list代替
        List<String> s2 = new ArrayList<>();
        for (String l : ls) {
            //如果是一个数就加入到s2
            if (l.matches("\\d+")){
                s2.add(l);
            }else if (l.equals("(")){
                s1.push(l);
            }else if (l.equals(")")){
                while (!s1.peek().equals("(")){
                    s2.add(s1.pop());
                }
                s1.pop();//将一对小括号弹出，消除一对括号
            }else{
                //当s1栈顶的运算符的优先级小于等于当前的优先级的时候，出栈运算
               //需要比较优先级高低的判断方法
                while (s1.size()!=0&&Operation.getValue(s1.peek())>=Operation.getValue(l)){
                    s2.add(s1.pop());
                }
                //还需要将l压入栈中
                s1.push(l);
            }
        }
        while (s1.size()!=0){
            s2.add(s1.pop());
        }
        return s2;//存放到list中正常输出
    }

    //将中缀表达式转换为list
    public static List<String> toInfixExpressionList(String s){
        List<String> ls = new ArrayList<>();
        int i = 0;//用户遍历中缀表达式字符串
        String str;//多位数拼接
        char c;
        do{
            //如果c是一个非数字，需要加入到ls中
            if ((c=s.charAt(i))<48||(c=s.charAt(i))>57){
                ls.add(""+c);
                i++;
            }else{
                //是一个数需要考虑多位数的问题
                str = "";//先置空
                while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=58){
                    str += c;//拼接多位数
                    i++;
                }
                ls.add(str);
            }
        }while (i<s.length());
        return ls;
    }


    //将一个逆波兰表达式，一次将数据和运算符放入
    public static List<String> getListString(String suffix) {
        //将suffix分割
        String[] s = suffix.split(" ");
        List<String> list = new ArrayList<>();
        for (String s1 : s) {
            list.add(s1);
        }
        return list;
    }

    //完成对逆波兰表达式的一个计算
    public static int calculate(List<String> ls) {
        //创建一个栈，只需要一个即可。
        Stack<String> stack = new Stack<>();
        for (String l : ls) {
            //使用正则表达式来取出数字
            if (l.matches("\\d+")) {
                //入栈
                stack.push(l);
            } else {
                //pop出两个数并运算，再入栈
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if (l.equals("+")) {
                    res = num1 + num2;
                } else if (l.equals("-")) {
                    res = num1 - num2;
                }else if (l.equals("*")){
                    res = num1 * num2;
                }else if (l.equals("/")){
                    res = num1/ num2;
                }else{
                    throw new RuntimeException("运算符有误!");
                }
                stack.push(res+"");
            }
        }
        //最后留在stack中的数据是结果。
        return Integer.parseInt(stack.pop());
    }
}

//编写一个类，返回运算符对应的优先级
class Operation{
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation){
        int res = 0;
        switch (operation){
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            default:
                break;
        }
        return res;

    }

}
